package LeetCode.Leet300_399.Leet330_339.Leet337;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Solution_2
 * @Author 孙天赐
 * @Date 2025/10/23 13:46
 * @Description TODO: 方法二   记忆化递归    2ms 23.33%
 */
class Solution_2 {
    public int rob(TreeNode root) {
        // 记录计算过的结果
        Map<TreeNode, Integer> memo = new HashMap<>();
        return robAction(root, memo);
    }

    int robAction(TreeNode root, Map<TreeNode, Integer> memo) {
        if (root == null)
            return 0;
        // 如果map里已经有记录则直接返回
        if (memo.containsKey(root))
            return memo.get(root);
        int money = root.val;
        // 偷父节点
        if (root.left != null) {
            // 跳过root->left
            money += robAction(root.left.left, memo) + robAction(root.left.right, memo);
        }
        if (root.right != null) {
            // 跳过root->right
            money += robAction(root.right.left, memo) + robAction(root.right.right, memo);
        }
        // 不偷父节点
        int money2 = robAction(root.left, memo) + robAction(root.right, memo);
        // 偷父节点与不偷父节点取最大值
        int res = Math.max(money, money2);
        // 记录到map中
        memo.put(root, res);
        return res;
    }
}
